package Leetcode第一期;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author : K k
 * @date : 15:56 2020/10/14
 * 在给定的网格中，每个单元格可以有以下三个值之一：
 * <p>
 * 值 0 代表空单元格；
 * 值 1 代表新鲜橘子；
 * 值 2 代表腐烂的橘子。
 * 每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
 * <p>
 * 返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
 * 示例 1：
 * 输入：[[2,1,1],[1,1,0],[0,1,1]]
 * 输出：4
 */
public class 腐烂的橘子_994 {
    public int orangesRotting(int[][] grid) {
        int N = grid.length;
        int M = grid[0].length;
        int count = 0;//新鲜橘子的个数
        int minute = 0;
        Queue<int[]> queue = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (grid[i][j] == 1) {
                    count++;
                }
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                }
            }
        }
        while (count > 0 && !queue.isEmpty()) {
            minute++;
            int n = queue.size();
            for (int k = 0; k < n; k++) {
                int[] position = queue.poll();
                int i = position[0];
                int j = position[1];
                //四个方向
                if (i - 1 >= 0 && grid[i][j] == 1) {
                    grid[i - 1][j] = 2;//感染
                    count--;
                    queue.offer(new int[]{i - 1, j});
                }
                if (j - 1 >= 0 && grid[i][j - 1] == 1) {
                    grid[i][j - 1] = 2;//感染
                    count--;
                    queue.offer(new int[]{i, j - 1});
                }
                if (i + 1 <= N && grid[i][j] == 1) {
                    grid[i + 1][j] = 2;//感染
                    count--;
                    queue.offer(new int[]{i + 1, j});
                }
                if (j + 1 <= M && grid[i][j + 1] == 1) {
                    grid[i][j + 1] = 2;//感染
                    count--;
                    queue.offer(new int[]{i, j + 1});
                }
            }
        }
        if (count != 0) {
            return -1;
        } else {
            return minute;
        }
    }

    public static int find(int n) {
        int count = 0;

        for (int i = 1; i <= 10000; i++) {
            for (int j = i+1; j <= 10000; j++) {
                if (i + j <= n || j-i >= n) {
                    continue;
                }
                if (i == n || j == n || j == i) {
                    //相等直接跳过
                    continue;
                }
                if (i < n && j < n) {
                    if (i * i + j * j == n * n) {
                        //n最大
                        count++;
                    }
                } else if (j > n && j > i) {
                    // j最大
                    if (i * i + n * n == j * j) {
                        count++;
                    }
                } else if (i > n && i > j) {
                    // i最大
                    if (j * j + n * n == i * i) {
                        count++;
                    }
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(腐烂的橘子_994.find(24));
    }

}
